class Skiplist {
    public:
        static const int level = 8;
        struct Node
        {
            int _val;
            vector<Node*> next;
            Node(int val = -1):_val(val) {
                next.resize(level, nullptr);
            }
        }*head;
        Skiplist() {
            head = new Node(-1);
        }
        ~Skiplist() {
            auto tmp = head;
            auto next = head;
            while (tmp) {
                next = next->next[0];
                delete tmp;
                tmp = next;
            }
        }
        void find(vector<Node*>& vn, int target) {
            Node* p = head;
            for (int i = level - 1; i >= 0; i--) {
                while (p->next[i] && p->next[i]->_val < target) {
                    p = p->next[i];
                }
                vn[i] = p;
            }
        }
        bool search(int target) {
            vector<Node*> vn(level);
            find(vn, target);
            auto p = vn[0]->next[0];
            return (p && p->_val == target);
        }
    
        void add(int num) {
            vector<Node*> vn(level);
            find(vn, num);
            auto newNode = new Node(num);
            for (int i = 0; i < level; i++) {
                newNode->next[i] = vn[i]->next[i];
                vn[i]->next[i] = newNode;
                if (rand() % 2) break;
            }
        }
    
        bool erase(int num) {
            vector<Node*> vn(level);
            find(vn, num);
    
            auto p = vn[0]->next[0];
            if (!p || p->_val != num) return false;
            
            for (int i = 0; i < level && vn[i]->next[i] == p; i++) {
                vn[i]->next[i] = p->next[i];
            }
            delete p;
            return true;
        }
    };
    
    
    /**
     * Your Skiplist object will be instantiated and called as such:
     * Skiplist* obj = new Skiplist();
     * bool param_1 = obj->search(target);
     * obj->add(num);
     * bool param_3 = obj->erase(num);
     */